The background description includes information that may be useful in understanding the present invention. It is not an admission that any of the information provided herein is prior art or relevant to the presently claimed invention, or that any publication specifically or implicitly referenced is prior art.
All publications herein are incorporated by reference to the same extent as if each individual publication or patent application were specifically and individually indicated to be incorporated by reference. Where a definition or use of a term in an incorporated reference is inconsistent or contrary to the definition of that term provided herein, the definition of that term provided herein applies and the definition of that term in the reference does not apply.
Computer systems (“host systems” or “host computer systems”) utilize non-volatile storage to store data. The data can then be retrieved, fetched, analyzed, processed, and restored by one or more computer system in the future. The main advantage to store data in non-volatile storages is for persistently storing data, which allows access to the data after power cycling of the host computer system and allows other computer systems to access the same data.
Today, due to ongoing demand for high speed data storage, digital storage units in both consumer and enterprise levels incorporate one or more internal circuitries to assist in storing and retrieving data from the associated host computer system in the non-volatile memories disposed in the storage unit. The internal circuitries enable the non-volatile storage unit to process large amount of host system data more efficiently.
The host system provides a set of logical addresses to represent different sectors in a logical memory. Each logical address represents one distinct sector of the logical memory (the smallest size of data the operating system (OS) can read and/or write into storage units). A logical address is used by the non-volatile storage controller to store and or retrieve the requested host system data. However, due to the non-volatile storage system's architecture, and the difference among internal circuitries in different non-volatile storage systems, the host logical addresses needs to be translated into actual non-volatile storage unit's physical addresses. The difference is inherent to actual non-volatile storage elements' architecture, for example, NAND flash non-volatile storage elements have a minimum read and/or program operation (write) size of 8 kilobyte (KB) or 16 KB, while a typical OS has a sector size of 4 KB. This discrepancy requires the Non-volatile Storage unit to keep track of mappings between host system logical addresses and non-volatile physical addresses. The mappings are usually stored as a logical to physical address translation table.
As an example, on the event that the host system requests a read operation on one particular 4 KB sector, the corresponding non-volatile storage unit will fetch a sector having its minimum required operation data size of 16 KB and provide the host system the requested 4 KB data chunk. The remaining data within the 16 KB sector will be dumped by the non-volatile storage controller for this operation. As it is obvious to the reader, if the host system issues a series of random write operations of 4 KB each, the non-volatile storage controller needs to provide a system and method to improve this mismatch, and eliminate the waste of storage unit individual internal sectors due to this large size discrepancy.
Today, many non-volatile storage controllers provide internal tables to keep track of the mappings between host system logical addresses and non-volatile storage physical addresses to resolve the sector size differences. The main issue with these tables is that as the size of non-volatile storage units increases, the logical to physical address translation table size will increase linearly. For example, a 4 terabyte (TB) non-volatile storage capable of processing 4 KB sectors will require a table with 1 billion row entries, where each row is capable of holding a logical address, a physical address, and some additional bits for housekeeping, which translates to a translation table size in excess of 4 gigabyte (GB) in size. The controller needs to have large enough size of internal memory to keep track of this translation and any additional data move around within the non-volatile storage unit due to the non-volatile Storage elements' architecture, and needs at all time the non-volatile storage unit be powered up and fully functional.
The address translation operation is required for each and every host system operation request. Collective, they increase processing time (latency), lower overall bandwidth (speed), increase overall product power consumption, increased overall thermal usage of product, and increase the total cost of operation of a non-volatile storage unit.
Thus, there remains a need for a system and method that improves the speed and memory usage of logical to physical address translation within a non-volatile storage unit.